package main

import "sort"

// 128.最长连续序列
func main() {
	//strs := []int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}
	strs := []int{9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6}
	res := longestConsecutive2(strs)
	print(res)
}

func longestConsecutive(nums []int) int {
	sort.Ints(nums)
	max := 0
	currMax := 0
	lastNum := -109
	for idx, n := range nums {
		if idx == 0 {
			currMax = 1
		} else if lastNum+1 == n { // 如果连续
			currMax++
		} else if lastNum == n {
			// 如果相同，不处理
		} else { // 不连续了
			if currMax > max {
				max = currMax
			}
			currMax = 1
		}
		lastNum = n
	}
	if currMax > max {
		max = currMax
	}
	return max
}

func longestConsecutive2(nums []int) int { // 使用go语言这么写，超时了
	res := 0

	newSet := make(map[int]int)
	for _, num := range nums {
		newSet[num] = num
	}

	for _, num := range nums {
		if _, exists := newSet[num-1]; !exists {
			currMax := 1
			currNum := num
			isSeq := true
			for isSeq {
				if _, es := newSet[currNum+1]; es {
					currMax++
					currNum++
				} else {
					isSeq = false
				}
			}
			if currMax > res {
				res = currMax
			}
		}
	}

	return res
}

//class Solution {
//    public int longestConsecutive(int[] nums) {
//    int ans = 0;
//    Set<Integer> numsSet = new HashSet<>();
//    for (int i = 0; i < nums.length; i++) {
//      numsSet.add(nums[i]);
//    }
//    for (Integer num : numsSet){
//      if (!numsSet.contains(num - 1)){
//        int currMaxLength = 1;
//        int currNum = num;
//        while (numsSet.contains(currNum + 1)){
//          currMaxLength++;
//          currNum++;
//        }
//        ans = Math.max(ans, currMaxLength);
//      }
//    }
//    return ans;
//    }
//}

// 128. 最长连续序列
//中等
//1.9K
//相关企业
//给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//
//请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
//
//示例 1：
//
//输入：nums = [100,4,200,1,3,2]
//输出：4
//解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
//示例 2：
//
//输入：nums = [0,3,7,2,5,8,4,6,0,1]
//输出：9
//
//
//提示：
//
//0 <= nums.length <= 105
//-109 <= nums[i] <= 109
